package org.example.myleet.rosalind.aspc;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.countSpecificSubSet(3, 6);
        solution.countSpecificSubSet(647, 1705);
    }

    private static final int MOD_BASE = 1000000;

    private final Map<String, Integer> combinations = new HashMap<>(1000000);

    public void countSpecificSubSet(int m, int n) {
        //空集合在本题中不算一个subSet
        int count = 0;
        for (int i = m; i <= n; ++i) {
            count += calculateCombination(n, i);
            count %= MOD_BASE;
        }
        System.out.println(count);
    }

    //递推法计算组合数的最后6位数字，由于递推法计算组合数是通过递归和加法实现的，因此可以通过取模计算保留组合数结果的最后6位数字
    private int calculateCombination(int n, int m) {
        String key = n + "_" + m;
        Integer combination = combinations.get(key);
        if (null != combination) {
            return combination;
        }
        if (m == 1) {
            combinations.put(key, n);
            return n;
        }
        if (n == m) {
            combinations.put(key, 1);
            return 1;
        }
        combination = calculateCombination(n - 1, m - 1) + calculateCombination(n - 1, m);
        combination %= MOD_BASE;
        combinations.put(key, combination);
        return combination;
    }
}
